#include "MemoryProfessor.h"
#include <malloc.h>
#include <new.h>


CMemoryProfessor::CMemoryProfessor(){
	m_pMemory = NULL;
	m_pFreeHeader = NULL;
	m_pFoot = NULL;
}

CMemoryProfessor::~CMemoryProfessor(){
	free(m_pMemory);
}

void CMemoryProfessor::Init(unsigned int unBytesAlloted){
	//Allocate a pool of memory specified by the user
	m_pMemory = (char*)malloc(unBytesAlloted);
	m_unSize = unBytesAlloted;

	char* pPlaceholder = m_pMemory;
	//Set up the start and end of the pool
	m_pFreeHeader = new(pPlaceholder) MemHeader;
	m_pFreeHeader->m_unSize = m_unSize-sizeof(MemHeader)-sizeof(MemFooter);
	m_pFreeHeader->m_pNext=m_pFreeHeader;
	m_pFreeHeader->m_pPrev=m_pFreeHeader;
	pPlaceholder = (char*)m_pFreeHeader;
	m_pFoot = new(pPlaceholder+sizeof(MemHeader)+m_pFreeHeader->m_unSize) MemFooter;
	m_pFoot->m_nSize = m_pFreeHeader->m_unSize;
}

char* CMemoryProfessor::Allocate(unsigned int unAllocSize){
	//If there is no free memory just return
	if(m_pFreeHeader==NULL)
		return NULL;
	MemHeader* pCurrHeader = m_pFreeHeader;
	MemFooter* pCurrFooter = NULL;
	char* pCurrLocation = NULL;
	//Loop through all the headers
	do{
		//Check if there is enough room in the current header, if there is allocate data and make a new free header.  Adjust list accordingly
		if(((pCurrHeader->m_unSize&USEDBIT)==0)&&pCurrHeader->m_unSize>=unAllocSize+sizeof(MemHeader)+sizeof(MemFooter)){
			pCurrLocation = (char*)pCurrHeader+sizeof(MemHeader)+unAllocSize;
			pCurrFooter = (MemFooter*)pCurrLocation;
			pCurrFooter->m_nSize=unAllocSize|USEDBIT;
			pCurrLocation+=sizeof(MemFooter);
			((MemHeader*)pCurrLocation)->m_unSize=pCurrHeader->m_unSize-(unAllocSize+sizeof(MemHeader)+sizeof(MemFooter));
			((MemHeader*)pCurrLocation)->m_pNext = pCurrHeader->m_pNext;
			((MemHeader*)pCurrLocation)->m_pPrev = pCurrHeader;
			pCurrHeader->m_pNext=(MemHeader*)pCurrLocation;
			if(pCurrHeader->m_pPrev==pCurrHeader)
				pCurrHeader->m_pPrev=(MemHeader*)pCurrLocation;
			pCurrHeader->m_unSize=pCurrFooter->m_nSize;
			if(m_pFreeHeader->m_unSize&USEDBIT){
				m_pFreeHeader=(MemHeader*)m_pMemory;
				do{
					if((m_pFreeHeader->m_unSize&USEDBIT)==0)
						break;
					m_pFreeHeader = m_pFreeHeader->m_pNext;
				}while((char*)m_pFreeHeader!=m_pMemory);
			}
			return (char*)pCurrHeader+sizeof(MemHeader);
		}
		pCurrHeader = pCurrHeader->m_pNext;
	}while(pCurrHeader!=m_pFreeHeader);
	//There wasn't enough free space, return NULL
	return NULL;
}

void CMemoryProfessor::Deallocate(void* p_vData){
	char* pData = (char*)p_vData;
	//If this pointer isn't in range just return
	if(pData<m_pMemory||pData>(char*)m_pFoot)
		return;
	MemHeader* pCurrHeader=(MemHeader*)m_pMemory;
	MemFooter* pCurrFooter = NULL;
	//As long as the pointer isn't null and there is a header look for the pointer
	while(pData&&pCurrHeader){
		//If it's the correct header deallocate the memory
		if((char*)pCurrHeader+sizeof(MemHeader)==pData){
			//There's no free space, no need to merge.
			if(m_pFreeHeader==NULL){
				pCurrHeader->m_unSize=pCurrHeader->m_unSize&~USEDBIT;
				pCurrFooter = (MemFooter*)((char*)pCurrHeader+sizeof(MemHeader)+pCurrHeader->m_unSize);
				pCurrFooter->m_nSize=pCurrHeader->m_unSize;
				m_pFreeHeader=pCurrHeader;
				return;
			}
			//There's free memory on both sides, merge both.
			else if(pCurrHeader!=(MemHeader*)m_pMemory&&(pCurrHeader->m_pNext->m_unSize&USEDBIT)==0&&(pCurrHeader->m_pPrev->m_unSize&USEDBIT)==0){
				pCurrHeader->m_unSize=pCurrHeader->m_unSize&~USEDBIT;
				pCurrHeader=pCurrHeader->m_pPrev;
				pCurrHeader->m_unSize=pCurrHeader->m_unSize&~USEDBIT;
				MemHeader* pRightHeader = pCurrHeader->m_pNext->m_pNext;
				pCurrHeader->m_pNext=pRightHeader->m_pNext;
				if(pCurrHeader->m_pPrev==pRightHeader)
					pCurrHeader->m_pPrev=pCurrHeader;
				pCurrHeader->m_unSize+=pRightHeader->m_pPrev->m_unSize+pRightHeader->m_unSize+(sizeof(MemFooter)<<1)+(sizeof(MemHeader)<<1);
				return;
			}
			//There's free memory to the right, merge right.
			else if((pCurrHeader->m_pNext->m_unSize&USEDBIT)==0){
				pCurrHeader->m_unSize=pCurrHeader->m_unSize&~USEDBIT;
				pCurrHeader->m_unSize+=pCurrHeader->m_pNext->m_unSize+sizeof(MemFooter)+sizeof(MemHeader);
				if(pCurrHeader->m_pPrev==pCurrHeader->m_pNext)
					pCurrHeader->m_pPrev=pCurrHeader;
				pCurrHeader->m_pNext=pCurrHeader->m_pNext->m_pNext;
				pCurrFooter = (MemFooter*)((char*)pCurrHeader+sizeof(MemHeader)+pCurrHeader->m_unSize);
				pCurrFooter->m_nSize=pCurrHeader->m_unSize;
				return;
			}
			//There's free memory to the left, merge left.
			else if(pCurrHeader!=(MemHeader*)m_pMemory&&(pCurrHeader->m_pPrev->m_unSize&USEDBIT)==0){
				pCurrHeader->m_unSize=pCurrHeader->m_unSize&~USEDBIT;
				pCurrHeader=pCurrHeader->m_pPrev;
				pCurrHeader->m_unSize+=pCurrHeader->m_pNext->m_unSize;
				if(pCurrHeader->m_pPrev==pCurrHeader->m_pNext)
					pCurrHeader->m_pPrev=pCurrHeader;
				pCurrHeader->m_pNext=pCurrHeader->m_pNext->m_pNext;
				pCurrFooter = (MemFooter*)((char*)pCurrHeader+sizeof(MemHeader)+pCurrHeader->m_unSize);
				pCurrFooter->m_nSize=pCurrHeader->m_unSize;
				return;
			}
			else{
				pCurrHeader->m_unSize=pCurrHeader->m_unSize&~USEDBIT;
				pCurrFooter = (MemFooter*)((char*)pCurrHeader+sizeof(MemHeader)+pCurrHeader->m_unSize);
				pCurrFooter->m_nSize = pCurrHeader->m_unSize;
				if(m_pFreeHeader==NULL)
					m_pFreeHeader=pCurrHeader;
				return;
			}
		}
		pCurrHeader=pCurrHeader->m_pNext;
	}
}
